﻿#define _CRT_SECURE_NO_WARNINGS 1

//class Solution {
//public:
//    int findNumberOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return 1;
//        vector<int> f(n, 1), g(n, 1);
//        unordered_map<int, int> hash;
//        int maxlen = 0;
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = i - 1; j >= 0; j--)
//            {
//                if (nums[i] > nums[j])
//                {
//                    if (f[j] + 1 == f[i])
//                    {
//                        g[i] += g[j];
//                    }
//                    else if (f[j] + 1 > f[i])
//                    {
//                        f[i] = f[j] + 1;
//                        g[i] = g[j];
//                    }
//                }
//            }
//            maxlen = max(maxlen, f[i]);
//        }
//        for (int i = 0; i < n; i++) hash[f[i]] += g[i];
//        auto it = hash.find(maxlen);
//        return it->second;
//    }
//};

//class Solution {
//public:
//    int findLongestChain(vector<vector<int>>& pairs) {
//        sort(pairs.begin(), pairs.end());
//        int n = pairs.size();
//        int maxlen = 1;
//        vector<int> dp(n, 1);
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = i - 1; j >= 0; j--)
//            {
//                if (pairs[i][0] > pairs[j][1])
//                {
//                    dp[i] = max(dp[j] + 1, dp[i]);
//                    maxlen = dp[i];
//                }
//            }
//        }
//        return maxlen;
//    }
//};

